package com.newcapec.utils;

public class ArrayUtil {
    private ArrayUtil(){}
    //冒泡排序
    //public static void
    //归并排序
    /**
     * 快速排序---归并排序
     * @param arr  要被排序的数组
     * @param low  数组起始位置
     * @param high 数组结束为止
     */
    public static void sort(int[] arr,int low,int high){
        int i,j,temp;
        if(low>=high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];

        while (i<j) {
            //先看右边，依次往左递减
            //右边查找比基准点小的值
            //同时要注意i与j的值
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边，依次往右递增
            //左边要找比基准点大的值
            //同时也要注意i与j的值
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            //注意i不能等于j
            //i==j时没必要交换
            if (i<j) {
                int t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //如果到这一步一定是i==j
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归调用左半数组
        sort(arr, low, j-1);
        //递归调用右半数组
        sort(arr, j+1, high);
    }

    //普通查找
    //二分查找
    /**
     * 二分查找/折半查找
     * 注意:使用该算法查找元素要求数组一定已经排序
     * @param arr  要被查找的数组
     * @param key  要查找的元素
     * @return   如果查找到，返回true，没有查找，返回false
     */
    public static boolean binarySearch(int[] arr,int key){
        int begin = 0;
        int end = arr.length-1;
        int middleIndex = (end+begin)/2;
        while(begin <= end) {
            if (key > arr[middleIndex]) {
                begin = middleIndex + 1;
                middleIndex = (end+begin)/2;
            } else if (key < arr[middleIndex]) {
                end = middleIndex - 1;
                middleIndex = (end+begin)/2;
            } else if (key == arr[middleIndex]) {
                return true;
            }
        }
        return false;
    }
    //数组去重
    /**
     * 去除数组中重复元素
     * @param arr  原始数组
     * @return     去重后的新数组
     */
    public static int[] distant(int[] arr){
        int n = arr.length;
        for(int i = 0; i < n-1; i++){
            for(int j = i+1; j < n ;j++){
                if(arr[i] == arr[j]){
                    //此时两个一样
                    for(int k = j; k< n-1; k++){
                        arr[k] = arr[k+1];
                    }
                    n--;
                    j--;
                }
            }
        }
        int[] newArr = new int[n];
        for(int i = 0; i < newArr.length; i++){
            newArr[i] = arr[i];
        }
        return newArr;
    }
    //数组打印
}
